//
// Created by francklinson on 2021/7/14 AT 23:26.
//
//给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
//
//规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
//
//请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 把边缘的点都放进队列进行多源BFS
     * 进行两次 没搜索的标记为0；能被左、上的点搜索到的标记为1；第二次搜索时，如果记录矩阵对应位置是1，则加入答案
     * @param heights
     * @return
     */
    const int movement[4][2] = {{0,  1},
                                {0,  -1},
                                {1,  0},
                                {-1, 0}};

    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
        int m = (int) heights.size(), n = (int) heights[0].size();
        vector<vector<int>> seen(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        /// 第一次  从左 上 位置开始搜索
        // 左
        for (int i = 0; i < m; ++i) {
            q.emplace(i, 0);
            seen[i][0] = 1;
        }
        // 上
        for (int j = 1; j < n; ++j) {
            q.emplace(0, j);
            seen[0][j] = 1;
        }
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            int r = p.first, c = p.second;
            for (int i = 0; i < 4; ++i) {
                int nr = r + movement[i][0];
                int nc = c + movement[i][1];
                if (nr >= 0 and nr < m and nc >= 0 and nc < n and seen[nr][nc] == 0) {
                    // 大等于的 可以标记
                    if (heights[nr][nc] >= heights[r][c]) {
                        q.emplace(nr, nc);
                        seen[nr][nc] = 1;
                    }
                }
            }
        }
        /// 第二次 从右 下 位置开始
        /// 搜到seen==1 则可以同时汇入两股洋流
        vector<vector<int>> ansPoints; // 储存答案
        // 右
        for (int i = 0; i < m; ++i) {
            q.emplace(i, n - 1);
            if (seen[i][n - 1] == 1) ansPoints.push_back(vector<int>{i, n - 1});
            seen[i][n - 1] = 2;
        }
        // 下
        for (int j = 0; j < n - 1; ++j) {
            q.emplace(m - 1, j);
            if (seen[m - 1][j] == 1) ansPoints.push_back(vector<int>{m - 1, j});
            seen[m - 1][j] = 2;
        }
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            int r = p.first, c = p.second;
            for (auto i : movement) {
                int nr = r + i[0];
                int nc = c + i[1];
                if (nr >= 0 and nr < m and nc >= 0 and nc < n and seen[nr][nc] != 2) {
                    // 大等于的 可以标记
                    if (heights[nr][nc] >= heights[r][c]) {
                        if (seen[nr][nc] == 1) {
                            ansPoints.push_back(vector<int>{nr, nc});
                        }
                        q.emplace(nr, nc);
                        seen[nr][nc] = 2;
                    }
                }
            }
        }
        return ansPoints;

    }
};

int main() {
    vector<vector<int>> heights{{1, 2, 2, 3, 5},
                                {3, 2, 3, 4, 4},
                                {2, 4, 5, 3, 1},
                                {6, 7, 1, 4, 5},
                                {5, 1, 1, 2, 4}};
    Solution sol;
    auto ans = sol.pacificAtlantic(heights);
    for (auto &row:ans) {
        for (auto &x:row) {
            cout << x;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}

